1. Field of the Invention
The invention disclosed herein is related to the determining routes for interconnections or paths between terminals of interoperable components. More specifically, the invention is related to path-finding in accordance with constraints on directly-connected pairs of terminals to satisfy constraints globally applied to a circuit layout. Such methodology is applicable in such fields as automatic circuit path routing, or autorouting, of printed and integrated circuits.
2. Description of the Prior Art
Automatic electric circuit routers, or autorouters, are path-finding mechanisms for forming conductor paths in a circuit layout that meet predetermined design goals. The present invention is directed to providing features heretofore unavailable in traditional autorouters and these features will be detailed below. However, in order to properly describe the invention in terms of its numerous advantages, it is believed beneficial to first define certain terminology that is used both in the context of traditional autorouters as well as in the context of the present invention.
As used herein, a “design” is an Electronic Design Automation (EDA) database of information describing a Printed Circuit Board (PCB), and Integrated Circuit (IC), an IC package, or a System-in-Package (SiP). A “system”, then, is a set of designs. For example, the collection of electrical components depicted in FIG. 1A includes an IC 110 in an IC package 120, which is a component of a circuit board 130. Similarly, IC 170 is contained in an IC package 160, which is a component of circuit board 150. The circuit boards 130 and 150 are inserted into the backplane 140, through which various circuits on both circuit boards are coupled. The set of designs for the electronic system of FIG. 1A is a system, as used herein, as are any of the subsets of designs. Indeed, many of the various IC's and packages on circuit board 130 may be systems and it is to be made clear that one system may be a hierarchy of systems, each having an associated set of designs.
A “terminal” is a location on one or more layers of a design to which electrical signals might be connected. For a PCB, terminals are typically referred to as pins, pads, or balls. For an IC Package or SiP design, terminals are typically referred to as IC bumps or package balls. A terminal may also be a junction point, sometimes referred to as a virtual pin or a T-junction. Various terminals are illustrated in FIG. 1B, such as terminal 180 and terminal 186. Terminal 184 is an example of a T-junction terminal.
Often, multiple terminals are grouped together into what is referred to herein as a “component”. Such a component is depicted at both 210 and 240 of FIGS. 2A and 2B.
A “connection” is a pair of terminals that are to be electrically connected. As is shown in FIG. 2A, component 210 includes terminals 212 and 214 and component 240 includes terminals 242 and 244. Terminals 212 and 242 form a connection 220 and terminals 214 and 244 form a connection 230. A connection may alternatively be referred to as a “rat”, a “fly line” or a “rubber band”. A connection includes two terminals, a “source terminal”, such as shown at 212 and 214, and a “target terminal”, such as shown at 242 and 244.
A “route” is a particular path that implements a particular connection starting at a source terminal and ending at a target terminal. Exemplary routes for connections 220 and 230 of FIG. 2A are shown as routes 250 and 260, respectively, in FIG. 2B.
A “geometric route” is a path defined by a sequence of explicit geometric shapes, such as path segments or arcs, on one or more layers of a design. When a path transitions from one layer to another, the geometric shapes which form the transition between the layers are collectively referred to as a “via”. The geometric shapes forming the paths of a geometric route, as well as other geometric shapes that are embodied in a completed system, such as terminal pads and vias, will be referred to herein as “routing objects”.
A “topological route” is a representation of a path specified by what objects it is between. These objects may be terminals or other routes, or they may be “obstacles”, such as keep out areas, drill holes or any other geometric or topological items in the design. A single topological route represents a set of diffeomorphic geometric routes, i.e., a set of geometric routes that can be morphed into one another through a continuous sequence of perturbations without changing the route's path relative to any other terminal, route or obstacle. A topological route may or may not have associated geometric locations, which determine one or more possible geometric routes represented by the topological route.
A “net” is a collection of terminals that are to be electrically connected. In some cases, the connections are specified in advance, such as when a particular terminal must connect directly to another specified terminal. In other cases, the particular arrangement of the various connections of a net is determined by path-finding routines of the autorouter, possibly subject to constraints imposed by certain design rules. In the absence of any connectivity rules, for example, an autorouter may be allowed to change the collection of connections as needed, provided the new collection still connects all of the terminals of the net.
An “extended net” is a collection of nets that are electrically related. For example, if two nets are electrically connected through a passive device, such as a series resistor, then the two nets form an extended net, sometimes referred to as an “Xnet”. If the two nets are on different designs and are electrically connected through a backplane, then they form an extended net that is sometimes referred to as an “SXnet”. Other examples of extended nets exist, such as nets inside an IC connecting through an IC package to a PCB, or nets on a daughterboard connected to nets on a motherboard. An exemplary extended net is illustrated in FIG. 1A by terminals indicated by the arrows at the various circuits. In the example, a terminal on IC 110 is coupled through a terminal on package 120 to the circuit board 130. The terminal on circuit board 130 is coupled through a connector on backplane 140 to circuit board 150, to a terminal on package 160 and then to a terminal on IC 170, where the extended net is terminated. Such an extended net may be as depicted in FIG. 1B, where source terminal 180 is connected through bus 142 to target terminal 188.
A “pin pair” is any pair of terminals belonging to the same extended net. There may be a single connection between the two terminals, in which case, the pin pair will be referred to as a “direct connection” and a route implementing the direct connection will be referred to herein as a “direct route”. Alternatively, there may be a series of connections between terminals of the extended net that, as a group, form an “indirect connection”. Referring to FIG. 1B, the connection 194 between terminals 186 and 184 is a direct connection, as is connection 192, whereas the connection between terminals 180 and 186 is an example of an indirect connection. A “connection group” is any interconnected set of one or more direct connections, for example, a net, an extended net or a pin pair.
A “constraint”, characterized by a “type of constraint”, is a design rule that may be applied to one or more connection groups. For example, a “maximum length constraint” is a type of constraint that can be applied to a pin pair, a net or an extended net. When applied to a pin pair, the maximum length constraint limits the sum of the lengths of each of the segments implementing the routes of each of its connections.
A “constraint instance” is a particular type of constraint applied to a particular item of a design. For example, a design rule limiting the maximum length for a net A-B-C to 3.0 inches is a constraint instance of the maximum length type of constraint.
A “numeric constraint” is a type of constraint that is defined in terms of a specific range of numeric values. The values may represent distance, such as 5.0 mils (thousandth of an inch). Examples of such distance-based constraints include minimum length, maximum length, track width, and clearance or separation between two routing objects. The numeric values may also represent time, for example, to specify minimum delay and maximum delay. The numeric values may also represent other physical entities, such as maximum cross talk as specified by a maximum voltage on a victim net. Some numeric values will simply be an integral value, such as the maximum number of vias and maximum number of layers allowed.
A “selection constraint” is a type of constraint that is defined in terms of a range of alternatives. For example, “layer set group 2/3 or 5/6” is a selection constraint that specifies alternative groups of layers on which the placement of routing objects is concurrently allowed. In this example, it specifies that routes must be on layers 2 and 3 or on layers 5 and 6. In accordance with this example, the constraint would allow routing a connection entirely on layer 2 or it would allow routing entirely on layers 5 and 6. But, it would prohibit routing the connection on both layer 2 and layer 6.
A “match constraint” is a type of constraint that requires that the same numeric range be applied to two or more connection groups, but without specifying explicit values for that range. For example, a match delay applied to a set of connections may require that the delay on paths of each of the connections be within some range. In this case, the range is specified as a tolerance or difference between max and min, but the specific min and max values are not specified.
A “relative constraint” is a type of constraint where the numeric value is specified as a difference and a tolerance for that difference between two different connection groups. For example, a relative delay of 15 with a tolerance of 2 for a pin pair A-B with respect to pin pair C-D requires that the delay for the route between terminal A and terminal B minus the delay for the route between terminal C and terminal D must be no more than 17 units and no less than 13 units.
Where a constraint instance is of a type of constraint that is specified by a numeric value, the constraint instance may be evaluated in terms of “resources”. A “resource value” of a constraint instance is a quantitative value indicating an amount of the constraint's resources that is consumed by its routes. For example, if the sum of the segment lengths for routes of a currently routed net totals 3.5 inches, then the resource value is 3.5. While constraint instances are defined with appropriate units of length, time, voltage, etc., associated therewith, resource values are often defined and stored as unitless quantities.
A “local constraint”, as used herein, is a constraint instance that applies to a particular direct connection or some portion of a direct connection. A “global constraint” is any constraint instance that is not a local constraint. For example, any constraint defined on a net or an extended net with more than two terminals is a global constraint. Any constraint defined on a pin pair forming an indirect connection and not a direct connection is a global constraint.
An “interconnect solution” is a set of routes that implement all of the connections and that satisfy all of the constraints.
Essentially all autorouters have mechanisms to support local constraints, although the set of constraint types that each autorouter supports may widely vary from one vendor to another. Such a mechanism, which will be referred to herein as a “convergence strategy”, iteratively finds routes for each connection and finds variations for those routes, until all of the required connections have corresponding geometric routes that meet all of the constraints.
An exemplary tool for implementing a typical convergence strategy is that of the traditional Single Connection Router (SCR), which determines a new route for each particular connection. If the SCR uses a geometric representation of the design, then it finds a geometric route. If the SCR uses a topological representation of the design, then it finds a topological route that is later transformed to a specific geometric route. Regardless of the SCR type, the path is determined using a search expansion mechanism, where the search decisions are made in accordance with one or more “cost functions”. A cost function computes a numeric value indicative of the level of difficulty of geometrically installing the path in the design, where such value is referred to as a “cost”. The typical SCR attempts to find a path with the lowest possible cost.
In some autorouters, the cost functions implemented are very simple, such as is illustrated in FIG. 3A. As is depicted, the cost function returns a zero (0), for example, if the constraint is met, i.e. is below a specified limit, and a one (1) if the constraint is not met, or, in the example, if the value is over the limit. Using the exemplary cost functions, a total cost of 0 implies that all constraints have been met.
Other autorouters use more complex cost functions, such as that depicted in FIG. 3B, to return a very small cost metric if the constraint is met by a wide margin, i.e., under the threshold “X” and a very large value, sometimes referred to as “infinity”, if the constraint is far above its limit, i.e., over the threshold value “Z”. The complex cost functions may return some midrange values for resource values falling in regions between “X” and “Y” and higher midrange cost metrics for resource values falling between “Y” and “Z”. Such cost functions allow for a greater number of choices from which the router may decide a path's trajectory.
Typically, the convergence strategy initializes a set of cost functions and then tasks the SCR to find routes for some or all of the connections in a “routing pass”. The cost functions are often modified prior to another routing pass producing thereby an alternative route. The convergence strategy continues executing routing passes until routes are found for all connections that meet all constraints.
Traditional autorouters perform well under local constraints, but they often fail to adequately process global constraints. For example, consider a net X having a constraint instance requiring its six connections to be routed on layers 2 and 3 or on layers 5 and 6. Clearly, a decision must be made as to which pair of layers to use for all connections in the net. In typical autorouters, the SCR would attempt to find paths for each of the connections of the net X allowing use of layers 2 and 3 or layers 5 and 6. Then, it would examine the results and determine the most commonly used pair of layers. For example, it may discover that five of the connections were routed on layer 2 with a total etch length of 8 inches. Further, it might discover that one of the connections was routed on layer 6 with a total etch length of 1 inch. In this case, the layer pair 2 and 3 would be selected and the SCR would reroute the remaining connection using only layers 2 and 3.
The problem with this approach is that a complete interconnect solution might never be found. For example, consider the case where there is congestion around a terminal on both layers 2 and 3 that prevents a connection involving that terminal from being routed on layer 2 or 3. Constraining the entire net X to layers 2 and 3 would make it impossible to complete a connection between the terminals and hence impossible to ever find an interconnect solution.
In another example, consider the routing problem of FIGS. 4A-4D. As shown in FIG. 4A, a net X, shown by its terminal pair A-B at 410, has a length constraint of 5 inches plus or minus 0.01 inches relative to net Y, shown as terminal pair C-D at 420. After a first routing pass, as shown in FIG. 4B, it may be determined that net X is 4 inches long and that net Y is 1 inch long. To meet the constraint, the router might add 2 inches to the connection of net X, as shown in FIG. 4C. However, in future routing passes, it is possible that the route for pin pair C-D might be shoved to make room for some other routes. In order to meet the relative length constraint at that point, an elongation process might be add length to the path for pin pair A-B, as shown in FIG. 4D. This so-called “creep” may result in far longer routes than are actually required by the constraints.
In another approach used in existing autorouters, often referred to as a “greedy” approach, the SCR, and possibly other mechanisms, allow the unrestrained consumption of all unused resources. To illustrate, consider the example of FIGS. 5A-5B, where a net 400 includes terminals A-D, as shown at 415, 420, 425 and 430, respectively. Suppose there is a global constraint on net 400 that requires that no more than two vias on the entire net are allowed. As shown in FIG. 5B, suppose that pin pair A-C receives one via, as shown at 440. The greedy routing procedure would then restrict the other connections of the net to a maximum of one via, since one of the allowed two vias has been consumed. Now, suppose that pin pair B-C used that last via, as shown at 445. In this case, the last connection, pin pair C-D, would be precluded from using any vias and it is entirely possible that the pin pair B-C cannot be routed without one. When this occurs, the autorouter will fail to find an interconnect solution that meets the global constraint.
Traditional approaches in autorouting typically consider global constraints after processing local constraints. For designs with only a small number of constraints, the process converges to a reasonable solution rather quickly. However, as the number of constraints necessary to implement modern designs increases, this strategy is less successful more often.
Thus, given the state of current technology, there is an apparent need for a convergence strategy that allows an autorouter to find routes that implement all of the connections, while also satisfying many different and often competing global constraints.